This invention relates generally to distributed directory server systems, and more specifically to a system and method for maintaining referential integrity between objects in a distributed directory server system.
Personal computers or workstations may be linked in a computer network to allow the sharing of data, applications, files, and other resources. In a client/server network, the sharing of resources is accomplished through the use of one or more file servers. Each file server includes a processing unit that is dedicated to managing centralized resources and to sharing these resources with other file servers and/or various personal computers and workstations, which are known as the xe2x80x9cclientsxe2x80x9d of the server.
Directories and directory services are often provided to enable an environment for a digital identity of a particular resource. One example of a directory service is Novell Directory Services (xe2x80x9cNDSxe2x80x9d) for Novell Netware networks, as provided by Novell, Inc. of Provo, Utah. NDS provides a logical tree-structure view of all resources on the network so that users can access them without knowing where they""re physically located.
A directory tree can be partitioned in to several smaller sub-trees that are stored on many file servers. These partitions are said to be xe2x80x9creplicatedxe2x80x9d on the servers. Each file server in the tree may contain anywhere from no replica of any partition to a replica of each partition.
Two important concepts in understanding the internal workings of NDS are external references and backlinks. An external reference is a reference to an entry that is not physically located on the local server. An external reference allows a reference to an entry without duplicating the entry on every server in the directory tree. External references are created for several reasons, including to ensure tree connectivity, to provide for authentication, and to refer to a nonlocal entry that is referenced in the attribute of a local entry.
A corresponding attribute to the external reference is the backlink. A backlink is stored as an object attribute to keep track of external references to the object. The directory uses a xe2x80x9cBackLinkxe2x80x9d attribute to keep track of servers holding external references of an entry. The BackLink attribute has two parts, including the Distinguished Name(s) of the server(s) holding the external reference (this name is commonly referred to as the Remote Server Name) and the Entry ID of the external reference on the remote server (usually referred to as the Remote ID). When creating an external reference to an entry, NDS also schedules the creation of a BackLink attribute for the entry. Periodically, a backlink process checks the external reference to see if the original entry still exists and if there is a reason for the external reference to continue to exist. If the external reference is not needed, NDS removes it.
The backlink process enables easy maintenance of the external references by periodically verifying the remote server name and remote ID of each BackLink attribute of entries. When an entry is deleted, backlinks make it possible for all references to the entry to be deleted. Backlinks also facilitate renaming and moving entries, because the corresponding changes can be made to the external references through the operation of the backlink process. Thus, the backlink process helps to maintain the integrity of external references by allowing them to be updated to reflect the changes made to the objects they refer to. The back link process resolves external references to make sure there is a real entry that it refers to, and for real entries the process makes sure that an external reference exists. A local bit in each external reference is used to keep track of the status of backlinks.
When a server creates an external reference to an entry, it sends a CreateBackLink request to a server holding a writable copy of the entry. This request contains the local Entry ID, the remote Entry ID, the remote server name, and two Time Stamps (Remote Creation Time and Remote Key Time). If the CreateBackLink request fails, it retries periodically until the BackLink attribute is created.
When a server removes an external reference from its local database, it sends a RemoveBackLink request to a server holding a writable entry for the entry. The request contains the Local Entry ID, the Remote Entry ID, the Server Entry ID, and the Time Stamp (Entry Creation Time). This RemoveBackLink request operation causes the backlink to be deleted.
As previously described, when NDS creates a new external reference for an entry not stored on the local server, NDS attempts to place on the real entry a backlink that points to the server that holds the external reference. For example, referring to FIGS. 1a and 1b, a tree 100 representing NDS includes two servers NS1 and NS2. The tree 100 is named, in this case, xe2x80x9cNovell,xe2x80x9d by its root object. As shown in FIG. 1b, the server NS1 stores a master replica of partitions xe2x80x9c[Root]xe2x80x9d and xe2x80x9cProvoxe2x80x9d and a read/write replica of a partition xe2x80x9cCore_OS.Provoxe2x80x9d and the server NS2 stores a master replica of the partition Core_OS.Provo. Partitions [Root], Provo and Core_OS.Provo are represented in FIG. 1a by partition objects designated 102, 104, and 106, respectively. Because the server NS2 does not have a replica of partition Provo, the server NS2 needs an external reference for partition Provo to connect partition Core_OS.Provo with [Root]. When NDS creates an external reference to partition Provo on server NS2, NDS places a backlink on server NS1""s copy of entry Provo pointing to NS2. In operation, server NS2 sends a CreateBackLink request that includes the backlink as an attribute value for the partition Provo.
The algorithm for creating a backlink is as follows. The server where the external reference is created sends a CreateBackLink request to the server holding a writable copy of the object. The server holding the original entry creates a backlink pointing to the server holding the external reference by adding to the original entry a BackLink attribute identifying the server holding the external reference and the identity of the external reference. The server holding the real entry returns a CreateBackLink reply. If this operation fails, NDS attempts to create the backlink nine more times at three-minute intervals. If all nine attempts fail, a background backlink process creates the backlink. The backlink process occurs every thirteen hours or as set by the system administrator and removes any expired or unnecessary external references from the system and creates and maintains any backlinks that NDS could not create when it created the external reference.
When NDS removes an external reference, the server holding the external reference requests that the server holding the real entry delete the backlink. NDS uses the RemoveBackLink process to delete a backlink. The server holding the external reference sends the server holding the real entry a RemoveBackLink request. The server holding the real entry deletes the backlink and returns a RemoveBackLink code indicating success or failure.
Referring to FIGS. 2a and 2b, a directory tree 200 includes a server S1 that stores a master replica of a partition a and a master replica of a partition b.a and a server S2 that stores a read/write (xe2x80x9cR/Wxe2x80x9d) replica of partition a and a master replica of a partition c.a. Partitions a, b.a, and c.a are respectively represented in FIG. 2a by partition objects a, b, and c. A printer object P1.c.a, represented in FIG. 2a by an object P1, in partition c.a is servicing a queue object Q1.b.a, represented in FIG. 2a by an object Q1, located in partition b.a. In this example, the queue object Q1.b.a will appear as a value of the queue attribute of the printer object P1.c.a. Because the server S2 does not have a replica of b.a., server S2 must have an external reference object of queue object Q1.b.a. The only reason the queue object Q1.b.a exists on server S2 is because the printer object P1.c.a has a reference to it.
As previously indicated, the server S1 has a master replica of the partition b.a; therefore, this server will contain the real object Q1.b.a and it must be able to locate all occurrences of the object Q1.b.a in the tree 200 in the event that the object is renamed or deleted. There is a replica ring that will identify every server that has a replica of the partition b.a but there must also be a way to locate the external reference objects that were created on servers that do not have a replica of the partition b.a, such as the server S2. Specifically, when the external reference for the object Q1.b.a is created on the server S2, a BackLink attribute is added to the object Q1.b.a on the server S1 that identifies that the server S2 contains an external reference thereto. That is the purpose of backlinks: to identify every server where an external reference to an object exists.
With backlinks, when an external reference is created on a server""s local database, all replicas of the object will get a backlink that points to the server where the external reference exists. The link from the object to the external reference is maintained at the server level. In practice, what occurs is that almost every server in the tree knows about every other server. Clearly, this is not desirable.
Because backlinks are server-specific, they do not scale well in trees with a large number of servers. This deficiency is difficult to see in the above example, but consider an example in which 100 servers in a tree have an external reference for the queue object Q1.b.a. In this case, there will be a BackLink attribute on the object Q1.b.a for each of these servers; i.e., 100 BackLink attributes on the single queue object.
Moreover, as backlinks identify a server, in this case, S2, that holds an external reference, if the identified server does not exist in a local replica of server S1, an external reference will be created for S2.c.a. on server S1.
In addition, it is not uncommon for backlinks to xe2x80x9corphanxe2x80x9d external references. Specifically, with backlinks, an external reference is created first and the backlink thereto is later added in a background process. In some cases, the latter process (i.e., the addition of the backlink) never happens and the external reference is orphaned.
Therefore, what is needed is an improved means for identifying servers on which an external reference to an object exists.
One embodiment, accordingly, employs Distributed Reference Links (xe2x80x9cDRLsxe2x80x9d) for managing the referential integrity between objects in a distributed system. In particular, DRLs perform a similar function as backlinks, but instead of identifying every server on which an external reference to an object exists, a DRL comprises a xe2x80x9cUsedByxe2x80x9d attribute added to an object that identifies a partition that has an external reference to that object.
In a preferred embodiment, DRLs specify a set of attributes, precedents, and algorithms that define how a resource can notify other resource managers of a change in the identity information of one of its objects. Using DRLs, before an external reference object is created, a xe2x80x9cUsedByxe2x80x9d attribute identifying the partition that reference the external reference is added to a R/W replica of the object prior to the creation of the external reference object.
A technical advantage achieved with the invention is that DRLs are not server specific and therefore scale better than backlinks in trees with a large number of servers.
Another technical advantage achieved with the invention is that DRLs are less likely to orphan external references than backlinks, as the DRL is created prior, rather than subsequent, to creation of the external reference.
Yet another technical advantage achieved with the invention is that DRLs can be extended to maintain the integrity of references stored in future agents.
Yet another technical advantage achieved with the invention is that DRLs decrease network traffic and the number of connections NDS maintains to other servers in a directory tree.
Still another technical advantage achieved with the invention is that DRLs facilitate backup of NDS objects.